# ---
# title: 1008. Construct Binary Search Tree from Preorder Traversal
# id: problem1008
# author: Idnigo
# date: 2021-01-30
# difficulty: Medium
# categories: Tree
# link: <https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/description/>
# hidden: true
# ---
# 
# Return the root node of a binary **search** tree that matches the given
# `preorder` traversal.
# 
# _(Recall that a binary search tree  is a binary tree where for every node, any
# descendant of `node.left` has a value `<` `node.val`, and any descendant of
# `node.right` has a value `>` `node.val`.  Also recall that a preorder
# traversal displays the value of the `node` first, then traverses `node.left`,
# then traverses `node.right`.)_
# 
# It's guaranteed that for the given test cases there is always possible to find
# a binary search tree with the given requirements.
# 
# **Example 1:**
# 
#     
#     
#     Input: [8,5,1,7,10,12]
#     Output: [8,5,10,1,7,null,12]
#     ![](https://assets.leetcode.com/uploads/2019/03/06/1266.png)
#     
# 
# 
# 
# **Constraints:**
# 
#   * `1 <= preorder.length <= 100`
#   * `1 <= preorder[i] <= 10^8`
#   * The values of `preorder` are distinct.
# 
# 
## @lc code=start
using LeetCode

function bst_from_preorder(preorder::AbstractVector{Int})
    if isempty(preorder)
        return nothing
    end
    i, f = 2, preorder[1]
    root = TreeNode(f)
    while i <= length(preorder) && preorder[i] < f
        i += 1
    end
    i -= 1
    root.left = bst_from_preorder(@view preorder[2:i])
    root.right = bst_from_preorder(@view preorder[i+1:end])
    root
end
## @lc code=end
